/*
Repeated DNA Sequences Total Accepted: 18675 Total Submissions: 94549 My Submissions Question Solution
All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG".
When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.

Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.

For example,

Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",

Return:
["AAAAACCCCC", "CCCCCAAAAA"].
*/

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <fstream>
#include <sstream>
#include <unordered_set>
#include <unordered_map>
#include "print.h"
using namespace std;

/**
* Definition for binary tree*/


void testForStack()
{
	stack<int> mystack;
	mystack.push(10);
	mystack.push(20);
	mystack.top() -= 5;
	cout << "mystack.top() is now " << mystack.top() << endl;
}

void testForIntToString()
{
	int a = 10;
	stringstream ss;
	ss << a;
	string str = ss.str();
	cout << str << endl;

	string str1 = to_string(a);

}


/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
	int getVal(char ch) {
		if (ch == 'A') return 0;
		if (ch == 'C') return 1;
		if (ch == 'G') return 2;
		if (ch == 'T') return 3;
	}

	vector<string> findRepeatedDnaSequences(string s) {
		set<string> st;
		vector<string> res;
		string str;
		if (s.length() < 10 || s == "") return res;
		int mp[1024 * 1024] = { 0 };
		unsigned int val = 0;
		for (int i = 0; i < 9; ++i) {
			val <<= 2;
			val |= getVal(s[i]);
		}
		for (int i = 9; i < s.length(); ++i) {
			val <<= 14;
			val >>= 12;
			val |= getVal(s[i]);
			++mp[val];
			if (mp[val] > 1) {
				str = s.substr(i - 9, 10);
				st.insert(str);
			}
		}
		for (set<string>::iterator i = st.begin(); i != st.end(); ++i) {
			res.push_back(*i);
		}
		return res;
	}
};
/**
* Your BSTIterator will be called like this:
* BSTIterator i = BSTIterator(root);
* while (i.hasNext()) cout << i.next();
*/

int main(int argc, char* argv[])
{

	//string s1 = "GAGAGAGAGAGA";
	string s1 = "GAGAGAGAGAGA";
	vector<string> strRes;



	Solution s;
	strRes = s.findRepeatedDnaSequences(s1);
	//cout << "The result is : " << result << endl;
	//result = s.partition(str);
	//stackTree.push(p->left);
	//stackTree.push(p->right);
	//if (s.isPalindrome(str1))
	//	cout << " True" << endl;
	//else
	//	cout << "false" << endl;
	system("pause");
	return 0;
}
//std::unordered_set<std::string> myset =
//{ "hot", "dot", "dog", "lot", "log" };

//std::cout << "myset contains:";
// for (auto it = myset.begin(); it != myset.end(); ++it)
//std::cout << " " << *it;
//;; std::cout << std::endl;

//TreeNode *root = new TreeNode(1);
//TreeNode *left = new TreeNode(2);
//TreeNode *right = new TreeNode(3);

//root->left = left;
//root->right = right;s